package ua.org.lapotko.mergeSort;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] input = { 8, 100, 6, 5, 4, 3, 2, 1, 0 ,-100,2};
		print(input);
		System.out.println();
		System.out.println(">>>>>>>>>>>>");
		int[] output = mergeSort(input);
		System.out.println(">>>>>>>>>>>>");
		print(output);
	}

	public static int[] mergeSort(int[] input) {
		// print(input);
		if (input.length > 2) {
			int newLength = input.length / 2;
			int[] array1 = new int[newLength];
			int[] array2 = new int[input.length - newLength];
			for (int i = 0; i < newLength; i++) {
				array1[i] = input[i];
			}
			int j = 0;
			for (int i = newLength; i < input.length; i++) {
				array2[j] = input[i];
				j++;
			}
			return merge(mergeSort(array1), mergeSort(array2));
		} else if (input.length == 1) {
			return input;
		} else {
			if (input[0] > input[1]) {
				int temp = input[0];
				input[0] = input[1];
				input[1] = temp;
				return input;
			} else {
				return input;
			}
		}
	}

	public static int[] merge(int[] input1, int[] input2) {
		print(input1);
		print(input2);
		System.out.print("=>");
		int newLength = input1.length + input2.length;
		int i1 = 0;
		int i2 = 0;
		int[] result = new int[newLength];
		for (int i = 0; i < newLength; i++) {
			if (input1[i1] < input2[i2]) {
				result[i] = input1[i1];
				i1++;
			} else {
				result[i] = input2[i2];
				i2++;
			}

			if (i1 == input1.length) {
				i++;
				for (; i < newLength; i++) {
					result[i] = input2[i2];
					i2++;
				}
			} else if (i2 == input2.length) {
				i++;
				for (; i < newLength; i++) {
					result[i] = input1[i1];
					i1++;
				}
			}

		}
		print(result);System.out.println();
		return result;
	}

	public static void print(int[] input) {
		System.out.print("[ ");
		for (int i = 0; i < input.length; i++) {
			System.out.print(input[i] + " ");
		}
		System.out.print("]");
	}

}
